﻿#define _CRT_SECURE_NO_WARNINGS 1	

#include <iostream>
using namespace std;

//155. 最小栈
//https://leetcode.cn/problems/min-stack/

#include <stack>

struct SS
{
    SS(int val = 0, int n = 0)
        :_val(val)
        , _n(n)
    {}

    int _val;    //值
    int _n;  //计数
};

class MinStack {
public:
    //自动调用自定义类型的构造函数
    MinStack()
    {}

    //小数入 mini栈
    void push(int val) {
        _st.push(val);

        //第一次
        if (_miniSt.empty())
            _miniSt.push(SS(val, 1));
        else if (_st.top() < _miniSt.top()._val)
            _miniSt.push(SS(val, 1));
        else if (_st.top() == _miniSt.top()._val)
            _miniSt.top()._n++;
    }

    void pop() {
        //只有相等时，才需要 pop 小栈
        if (_st.top() == _miniSt.top()._val)
        {
            _miniSt.top()._n--;

            if (_miniSt.top()._n == 0)
                _miniSt.pop();
        }

        _st.pop();
    }

    int top() {
        return _st.top();
    }

    int getMin() {
        return _miniSt.top()._val;
    }

private:
    stack<int> _st;
    stack<SS> _miniSt;
};

int main()
{
    MinStack M;

    M.push(2);
    M.push(0);
    M.push(3);
    M.push(0);

    int min = M.getMin();

    M.pop();

    min = M.getMin();

    M.pop();

    min = M.getMin();

    M.pop();

    min = M.getMin();

    cout << min << endl;

    return 0;
}

//JZ31 栈的压入、弹出序列
//https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&&tqId=11174&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking

class Solution {
public:
    bool IsPopOrder(vector<int> pushV, vector<int> popV) {
        //使用栈，模拟实现
        stack<int> s;

        int popi = 0;
        int pushi = 0;

        while (pushi < pushV.size())
        {
            s.push(pushV[pushi]);

            while (!s.empty() && popV[popi] == s.top())
            {
                //出栈
                s.pop();
                popi++;
            }

            pushi++;
        }

        return popi == popV.size();
    }
};